package practice;

import java.util.HashMap;
import java.util.Map;

/**
 * 算法练习第四天
 */
public class Day4 {

    /**
     * 除自身以外的乘积
     * 输入: nums = [1,2,3,4]
     * 输出: [24,12,8,6]
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] dp1 = new int[n];
        dp1[0] = 1;
        for(int i = 1; i < n; i++) {
            dp1[i] = dp1[i - 1] * nums[i - 1];
        }
        int[] dp2 = new int[n];
        dp2[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--) {
            dp2[i] = dp2[i + 1] * nums[i + 1];
        }
        int[] answer = new int[n];
        for(int i = 0; i < n; i++) {
            answer[i] = dp1[i] * dp2[i];
        }
        return answer;
    }

    /**
     * 和为k的子数组
     * 输入：nums = [1,1,1], k = 2
     * 输出：2
     * 此题需要进行转化：找到[0,i-1]位置中，有多少个前缀和为sum - i,sum为前缀和
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int count = 0;
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            count += map.getOrDefault(sum - k,0);
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return count;
    }
}
